class Point:

    def __init__(self, x, y):
        self.x = x
        self.y = y


    def __str__(self):
        return "(" + str(self.x) + ", " + str(self.y) + ")"

    def __eq__(self, p):
        return (self.x == p.x) and (self.y == p.y)
    
    def compare(self, p):
        pos = ""
        
        if (self.x >= p.x):
            pos = "S"
        else:
            pos = "N"
            
        if (self.y >= p.y):
            pos += "W"
        else:
            pos += "E"

        return pos

    def distancePP(self, p):
        return ((self.x-p.x)**2 + (self.y-p.y)**2)**0.5
    
            


class Node:

    def __init__(self):
        self.quad = {}

    def __str__(self):
        ret = str(self.point)

        ret += "["
        
        for k in self.quad.keys():
            ret += str(k)+":" + str(self.quad[k])

        ret += "]"
        return ret

    def setPoint(self, p):
        self.point = p

    def getPoint(self):
        return p

    point = property(setPoint, getPoint)
    

    def addPoint(self, p):
        pos = self.point.compare(p)
        if self.quad.has_key(pos):
            return self.quad[pos].addPoint(p)
        else :
            node = Node()
            node.point = p
            self.quad[pos] = node


    def recNN(self, point, pointTmp, distTmp):

        newDist = self.point.distancePP(point)

        if (newDist < distTmp):
            distTmp = newDist
            pointTmp = self.point

        
            


    
    def dfs(self):
        visit = [self.point]
        for k in self.quad.keys():
            visit.extend( self.quad[k].dfs() )
        return visit

        

class PQTree(Node):

    def __init__(self):
        Node.__init__(self)
        self.empty = True

    def addPoint(self, p):
        if self.empty :
            Node.setPoint(self, p)
            self.empty = False
        else:
            Node.addPoint(self, p)

    def nn(self, point):
        pointTmp = self.point
        distTmp  = self.point.distancePP(point)
        return recNN(self, point, pointTmp, distTmp)
        

    def __str__(self):
        return "PQTREE: " + Node.__str__(self)


    
def strPointList( lp ):
    res = ""
    for p in lp:
        res += str(p)
    return res  
        


def test():
   t = PQTree()
   t.addPoint(Point(10,10))
   t.addPoint(Point(1 , 1))
   t.addPoint(Point(8 , 8))
   t.addPoint(Point(15,15))
   t.addPoint(Point(13, 6))
   t.addPoint(Point(2 ,18))
   t.addPoint(Point(11, 3))
   t.addPoint(Point( 4,14))
   t.addPoint(Point( 7,17))
   t.addPoint(Point(12, 2))
   t.addPoint(Point(12,12))
   t.addPoint(Point( 6,13))
   t.addPoint(Point( 5, 9))
   print t
   print "DFS: " + strPointList( t.dfs() )
   return t

test()

    
    
